package com.xxd.algo.newcode.base02.class03;

/**
 * @author: XiaoDong.Xie
 * @create: 2021-04-26 12:41
 * @description:
 */
public class Mynacher {

    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    public static int maxLcpsLength(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        char[] str = manacherString(s); // 1221 ->  #1#2#2#1#
        int C = -1;
        int R = -1;
        int[] pArr = new int[str.length];
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < str.length; i++) {
            pArr[i] = R > i
                    ? Math.min(pArr[2 * C - i], R - i)
                    : 1;

            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]])
                    pArr[i]++;
                else
                    break;
            }

            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }

            max = Math.max(max, pArr[i]);
        }

        return max - 1;
    }
    
    public static void main(String[] args) {
        String str1 = "abc1234321ab";
        System.out.println(maxLcpsLength(str1));
    }
}
